#
# @lc app=leetcode.cn id=124 lang=python3
#
# [124] 二叉树中的最大路径和
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf # 节点值有负数,路径至少要有1个点,初始化为负无穷大
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None:
                return 0
            left_val = dfs(node.left) # 左子树最大路径和
            right_val = dfs(node.right) # 右子树最大路径和
            nonlocal ans
            # 拼接左子树,右子树路径
            ans = max(ans, left_val+right_val+node.val)
            # 当前node子树最大路径和,可能是负数,和0取最大值
            return max(max(left_val, right_val)+node.val, 0)
        dfs(root)
        return ans
# @lc code=end

